package com.learn.recursive;

/**
 * 总共N个位置，从M位置出发，需要走K步，最终到达P,有多少种走法
 * 当M在1位置，只能走到2，当M在N位置，只能走到N-1位置，其他则可以向左向右走
 */
public class RobertWalk {
    /**
     * @param M
     * @param N
     * @param P
     * @param K
     * @return
     */
    public int walkSize(int M, int N, int P, int K) {

        return walk(N, P, M, K);
    }

    /**
     * cur当前位置，res剩余位置
     *
     * @param N
     * @param P
     * @param cur
     * @param res
     * @return
     */
    public int walk(int N, int P, int cur, int res) {
        if (res == 0) {
            return cur == P ? 1 : 0;
        }

        if (cur == 1) {
            walk(N, P, 2, res - 1);
        }

        if (cur == N) {
            walk(N, P, N - 1, res - 1);
        }

        return walk(N, P, cur + 1, res - 1) + walk(N, P, cur - 1, res - 1);
    }


    //解法2，计划搜索，动态规划
    public int walkSize1(int M, int N, int P, int K) {
        int[][] cache = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                cache[i][j] = -1;
            }
        }
        return walk1(N, P, M, K, cache);
    }

    /**
     * cur当前位置，res剩余位置
     *
     * @param N
     * @param P
     * @param cur
     * @param res
     * @return
     */
    public int walk1(int N, int P, int cur, int res, int[][] cache) {
        if (cache[cur][res] != -1) {
            return cache[cur][res];
        }
        if (res == 0) {
            cache[cur][res] = cur == P ? 1 : 0;
            return cache[cur][res];
        }

        if (cur == 1) {

            cache[cur][res] = walk(N, P, 2, res - 1);
            return cache[cur][res];
        }

        if (cur == N) {
            cache[cur][res] = walk(N, P, N - 1, res - 1);
            return cache[cur][res];
        }

        cache[cur][res] = walk(N, P, cur + 1, res - 1) + walk(N, P, cur - 1, res - 1);
        return cache[cur][res];
    }
}
